【论文学习】AlphaCodium：从Prompt Engineering 到 Flow Engineering
在看新闻联播前，我们增加一篇产业理论的加餐学习。
最近 langchain 作者 Harrison 在一次演讲中提到了一篇论文《Code Generation with AlphaCodium- From Prompt Engineering to Flow Engineering》，提出了Flow Engineering的概念，对我们如何构建agent应该有所启发。
感谢宝玉老师科技文章翻译器加持，我对全篇又人工校对了一遍，整理分享如下：
摘要
代码生成与常见的NLP问题不同，它需要精确匹配目标编程语言的语法规则，识别程序的最佳执行路径及潜在的边界情况，关注问题描述中的众多细节，并解决其他编码中的特定问题和要求。
因此，自然语言生成中有效的众多优化策略和技巧，可能并不适用于代码任务。在这项工作中，我们提出了一种新的代码生成方法，名为AlphaCodium —— 一种基于测试的、多阶段的、面向代码的迭代流程，能够显著提升大语言模型在代码问题上的表现。我们在一个名为CodeContests 的挑战性代码生成数据集上测试了AlphaCodium，该数据集收录了来自Codeforces等平台的竞赛编程题目。
我们的方法能够一致且显著地改进生成代码的质量。例如，在验证集上，使用AlphaCodium方法后，GPT-4的准确率 pass@5 从19%提升至44%。我们认为，这项工作中获得的许多原则和最佳实践对于一般代码生成任务具有广泛的适用性。
1. 引言
由于代码生成任务需要在巨大的、结构化的程序可能空间中进行搜索，奖励信号（reward sigmal）是非常稀疏的。即使是针对同一个问题的正确解决方案也可能截然不同，而且判断一个不完整或错误的解决方案是否有价值是一个复杂的挑战——仅仅一处字符的改动就能彻底改变程序的行为。
由于代码生成任务的特殊性，那些为自然语言任务优化的常见prompt技巧可能在应用于代码生成时效果不佳。
最近的基于大规模Transformer的语言模型已经成功地生成了解决简单编程任务的代码。然而，现实世界中的代码问题往往更加复杂，它们通常由长篇的自然语言任务描述定义，包含了解决方案代码需要遵循的众多细节和规则。
CodeContests 是一个由 Codeforces 等竞赛编程平台策划的数据集，使得对于更具挑战性的代码问题的模型和方法评估成为可能，这些问题通常附带有详细的问题描述。私有测试集每个问题包含 200 多个未见过的测试，可以全面全面评估生成的代码，并将误报率降至最低。
首个针对CodeContests数据集的主要研究是DeepMind开发的代码生成系统AlphaCode，它采用了专门为竞赛编程任务调优的网络。AlphaCode可以生成大量（高达100万个）可能的解决方案，经过处理和聚类后，从中挑选出大约10个提交。尽管AlphaCode的成果令人印象深刻，但需要为代码任务特别调优的模型和庞大的计算负担，使得它在实际应用中不太可行。另一个项目CodeChain引入了一种新颖的推理框架，通过一连串基于子模块的自我修订来提高大语言模型在代码生成方面的性能。
在本文中，我们介绍了一个专注于代码生成的新流程——AlphaCodium。这一流程核心是一个迭代的过程，通过反复执行和修正针对input-output test 生成的代码来不断优化代码质量。
AlphaCodium flow 的两大关键在于：(a) 生成额外数据，如问题反思和测试推理（problem reflection and test reasoning），以促进迭代过程的深入；(b) 利用AI生成的 tests 来增强现有的 public tests。如图1所示，这个流程分为两大阶段：
首先是预处理阶段，我们在这一阶段通过自然语言深入分析问题； 其次是迭代代码生成阶段，在这里我们生成代码，并根据公开及AI生成的测试进行运行和修正。
Figure 1-(a) The proposed AlphaCodium flow.
Figure 1: AlphaCodium流程的工作原理及其贡献。在只使用模型的直接初始prompt来尝试解决编码问题时，模型往往难以找到有效的解决方案。通过在公开测试用例上反复迭代，虽然能够稳定并部分改善解决方案，但由于公开测试用例覆盖不全，仍然存在一些“盲点”。而采用完整的AlphaCodium流程，不仅包括了预处理阶段，还涵盖了在公开测试及AI生成的测试上进行的迭代，这使得解决方案得以进一步优化，显著提升了问题解决的成功率。
设计AlphaCodium flow时的一个重要发现是，与生成正确的代码解决方案相比，生成额外的有用测试要容易得多。这主要需要对问题有深入的理解、一定的洞察力以及基础的逻辑推理能力。生成这些额外的测试并不需要完全“解决”问题本身。
AlphaCodium流程还融入了一些新颖的、面向代码的设计理念、技巧和最佳实践，例如：
(1) 使用YAML结构化输出；
(2) 通过项目符号列表促进语义上的推理；
(3) 生成模块化的代码；
(4) 实施带双重验证的软决策；
(5) 鼓励探索性思考，并延后做出直接决策；
(6) 设立测试锚点。
与精心设计的单个prompt相比，AlphaCodium流程在处理CodeContests问题上能够一致且显著提升大语言模型的表现，无论是开源模型（如DeepSeek）还是闭源模型（如GPT）。以GPT-4为例，其在验证集上的pass@5准确率从19%提高到了44%。
AlphaCodium不仅超越了之前的研究成果，而且还大大降低了计算资源的需求——与AlphaCode相比，它减少了四个数量级的 LLM 调用次数，实现了更优的结果。
我们相信，本文中采用的许多原则和最佳实践对于更广泛的代码生成任务都具有参考价值。
此外，我们认为，使用像CodeContests这样更具挑战性、更复杂的测试集，可以使社区更有效地评估大语言模型的性能，相比之下，现今常见的如 HumanEval 这类简单的基准测试就显得不足够。
2. CodeContests 数据集
CodeContests是由 Google DeepMind 推出的一个具有挑战性的代码生成数据集，选取了来自Codeforces等竞赛编程平台的题目。该数据集涵盖了1万个可供大语言模型训练的编程题目，同时提供了用于评估模型解决复杂编码问题能力的验证集和测试集。
在本项工作中，我们没有专门训练一个模型，而是致力于开发一套适用于任何已经预训练好的、支持编程任务的大语言模型的代码生成流程，如GPT或DeepSeek。
因此，我们没有使用训练集，而是集中在CodeContests的验证集和测试集上，这两个集合分别包含了107个和165个问题。图2(a)给出了一个来自CodeContests数据集的典型问题示例。每个问题包含了问题描述和公开测试数据，可作为模型生成代码的输入。目标是生成能够对任何合法输入产生正确输出的代码解决方案。
此外，还有一个私有测试集用于评估提交的代码，这部分测试集对模型或参赛者是不可见的。
Figure 2-(a) 一个典型的 CodeContests 问题.
Figure 2-(b) AI 生成对问题的 self-reflection
Figure 2 展示了一个CodeContests数据集中典型问题的描述及其AI辅助的self-reflection示例。尽管原问题描述复杂且详细，通过精确的self-reflection，使得问题的表述变得更加清晰有序，进而促进了更优的代码解决方案的产生。
CodeContests数据集成为评估LLM在代码生成任务上的理想选择的原因包括：
与其他许多竞赛编程数据集不同，CodeContests利用了一个全面的私有测试集来避免误报的情况——每个问题的代码答案都必须通过 200 个私有输入输出测试。 大语言模型通常在关注细节上存在不足，因为它们倾向于将具体的问题描述转化为一个更为泛化的描述，这与它们训练时接触的常见情况相似。而现实世界的编程问题往往充满了对正确解决问题至关重要的细节。CodeContests数据集的独特之处在于，它故意设计了复杂而详尽的问题描述，充满了细节和微妙之处（参见图2(a)中的一个示例）。我们认为，这种对问题理解的深度让模型面临的挑战更接近现实生活中的情况，这是与那些问题描述更为简洁的常见代码数据集（如HumanEval）形成鲜明对比的。
图2(b)展示了模型对图2(a)中问题的深度反思。可以看到，通过精确的self-reflection，使得问题描述变得更加清晰和条理，这强调了在流程中对问题深入理解的重要性，这种理解极大可能促成正确代码解决方案的生成。
3. AlphaCodium Flow
3.1 概述
面对代码生成问题的复杂性，我们发现仅依靠单一prompt的优化甚至是思维链（COT），并不能在 CodeContests 上显著提升 LLM 的准确率。模型往往难以深入理解问题，经常产生错误的代码，或者是能通过公开测试但不能适用于私有测试的代码。传统适用于自然语言处理任务的流程，并不完全适合代码生成任务，后者有其独特的潜在特质——反复执行生成的代码并对照已知示例进行验证。
我们发现，与 NLP 中使用的常见提示工程技术不同，采用一个专门的、测试导向的、围绕迭代过程展开的代码生成流程，在解决CodeContest 问题时更为有效。这一流程特别强调反复运行并修正代码，以适应输入输出测试（参见图2(a)中的测试示例）。这种流程的两个关键组成部分包括：
(a) 在预处理阶段生成辅助迭代过程的额外数据，例如 self-reflection 和 public tests reasoning，
(b) 通过额外的AI生成测试来增强 public test 。
图1(a)展示了解决竞赛编程问题的 AlphaCodium 流程。该流程主要分为两个阶段：
预处理阶段是一个线性流程，AlphaCodium在这一阶段用自然语言对问题进行深入分析，
代码迭代阶段包括多个迭代阶段，AlphaCodium在此生成、执行并修正针对特定测试的解决方案代码。
3.2 Flow stages
本节将详细介绍AlphaCodium流程中的各个阶段（如图1(a)所示）：
问题反思（Problem reflection）
用简要的要点描述问题，涵盖问题的目标、输入、输出、规则、约束以及问题描述中的其他相关细节。
公共测试推理（Public tests reasoning）
详细解释每个测试输入如何得到其输出。
生成可能解决方案（Generate possible solutions）
列出2-3个可能的解决方案，并用自然语言进行描述。
解决方案排序（Rank solutions）
对可能的解决方案进行排名，选择在正确性、简洁性和鲁棒性方面“最好的解决方案”（不一定是“最高效”的解决方案）。
生成额外的AI测试（Generate additional AI tests）
为问题生成额外的6-8个多样化的输入输出测试，尝试覆盖原公开测试未包含的情况和方面。
初始代码解决方案（Initial code solution）
此阶段目标是生成问题的初始代码解决方案。关键是确保此代码足够接近正确解决方案，以使下一阶段的运行-修正迭代有更高的成功机会。
具体流程如下：
选择一个可能的解决方案，为之生成代码，并在选定的公开和AI测试上运行。
重复此过程，直至测试通过或达到尝试上限。
首个通过测试的代码，或与正确输出最为接近的代码（参见附录D），将作为后续步骤的基础代码。
在公开测试上迭代（Iterate on public tests）
从基础代码出发，对公开测试进行迭代运行。若代码在某个测试中失败，则根据错误信息尝试修正。
在AI生成的测试上迭代（Iterate on AI-generated Tests）
继续在AI生成的测试上进行运行-修正迭代，利用“测试锚点”（参见第4节）。
3.3 Additional insights
在这一节里，我们分享一些关于所提出的flow（流程）的其他洞察。
首先，flow 强调了知识的逐步累积——我们试图从简单问题开始，逐渐攻克更难的问题，过程中积累的知识和洞察将有助于我们解决后续更为困难的挑战。
例如， “problem reflection” 阶段的输出，可以作为如“generate possible solutions”等解决难题阶段的prompt输入。预处理阶段的成果对于后续最具挑战性且关键的“code iterations”阶段至关重要，我们在此尝试生成能够正确解决问题的代码。
在AlphaCodium的设计中，另一个关键的洞察是，相比于生成完整的解决方案代码，对于AI来说，生成更多的测试要更为简单。生成这些额外的测试主要依赖于对问题的理解以及基本的逻辑推理。 在生成有用的额外输入输出测试对时，并不需要彻底“解决”整个问题。
这与生成一个正确的解决方案代码形成鲜明对比，后者需要完整的算法解决方案，相当于准确解决任何可能的输入输出测试对。因此，我们能够生成更多的AI测试，并利用它们来优化代码创建阶段，正如图1(b)所描述的那样。我们进一步通过让模型关注原始公开测试未覆盖的方面（如处理大输入、边界情况等）来增强这些额外测试的作用。
还需要注意，某些步骤可以合并为一次大语言模型的调用，而图2(a)中展示的流程是一个概念性流程，突出了整个过程的关键步骤。实际操作中，通过结构化输出（参见第4节）可以将多个阶段合并为一次调用，这样不仅可以节省资源，还因为模型在同时处理特定任务时可能表现更优。
4 面向代码的设计理念 Code-Oriented Design Concepts
在本节中，我们将介绍一些在尝试解决代码生成问题时发现有益的额外设计概念、技巧和最佳实践。在图1中提出的AlphaCodium流程广泛使用了这些设计理念。
4.1 YAML结构化输出
使用结构化输出——要求模型以YAML格式生成输出，相当于给定的Pydantic类——是我们提出的流程中的关键组成部分。此类指令的示例（possible solutions阶段）如图3所示。
图3具有结构化输出的提示示例（possible solutions stage）
结构化输出消除了“提示工程”的大部分麻烦和暗知识要求，相反，它允许复杂任务以直接、类似代码的方式呈现。它还使得获得涉及多个阶段的复杂答案成为可能，代表了逻辑和方法论思维过程。
虽然新版本的GPT模型[5]支持JSON风格的输出，我们认为YAML输出更适合代码生成任务，详见附录B。
4.2 通过项目符号分析进行语义推理
当要求一个LLM对问题进行推理时，要求输出以项目符号格式呈现可以获得更好的结果。
项目符号鼓励对问题进行深入理解，并迫使模型将输出划分为逻辑语义部分，从而改善结果。
例如，对问题进行项目符号形式的自我反思（图2(b)），每个项目符号代表对问题不同部分的语义理解——总体描述、目标和规则、输入结构和输出结构。
4.3 LLMs在生成模块化代码方面表现更好
当要求LLMs生成一个长函数时，我们观察到结果不佳——代码经常包含bug或逻辑错误。
更糟的是，单个的整体代码损害了执行迭代修正的能力——即使给出错误信息，模型也难以定位并修复问题。当明确地要求模型：“将生成的代码分成具有意义的名称和功能的子函数”时，我们观察到生成的代码质量更高，错误更少，迭代修正阶段的成功率更高。
4.4 双重验证的软决策
LLMs往往会在需要思考、推理并做出严格、重要决策的代码任务中遇到困难。以生成问题的额外测试为例，很多时候，模型生成的一些测试将是完全错误的。通过双重验证过程，我们增加了一个额外的步骤：给定生成的输出，要求模型重新生成相同的输出，但在必要时进行更正。
例如，给定生成的AI test作为输入，要求模型重新生成相同的测试，同时更正错误的输出（如果存在）。
我们发现，这一双重验证步骤，在鼓励模型进行批判性思考和推理时，比直接询问是/否问题：“这个测试是否正确？”更有效。
4.5 推迟决策，尽量避免直接问题，留出探索空间
当我们就复杂问题直接询问模型问题时，我们总是会看到幻觉和错误答案。为了应对这一点，我们采用了从简单任务到困难任务的渐进式数据积累流程：
从最简单的任务开始——对问题进行自我反思，并对公共测试进行推理。 转向生成额外的AI测试，以及问题的可能解决方案 只有在我们获得了模型对上述任务的答案后，我们才转向实际的代码生成和运行-修复迭代。
作为另一个例子，我们更倾向于对几个可能的解决方案进行排名，而不是选择单一的算法解决方案，当生成初始代码时给予排名最高的解决方案优先权，但不是排他性的。
由于模型可能出错，因此最好避免不可逆转的决策，并为不同可能的解决方案进行探索和代码迭代留出空间。
4.6 测试锚点（Test anchors）
即使进行了双重验证，一些AI生成的测试也会是错误的。这使得对它们进行迭代变得具有挑战性——当测试失败时，我们如何知道是代码错误还是测试错误？
当我们直接询问模型“谁错了”时，我们经常看到幻觉，最终可能得到错误修正的代码。为了解决这个问题，我们使用了测试锚点（Test anchors）技术：
首先迭代公共测试，我们知道它们是正确的。完成后，将所有通过的测试设置为锚点测试（anchor tests）。 现在逐一迭代AI生成的测试。如果测试通过，将其添加到测试锚点列表中。 如果测试失败，假设是因为代码不正确，并尝试修复代码。但是，要求修正后的代码也必须通过所有已获得的测试锚点。结果，测试锚点将保护我们免受错误修正代码的影响。
对测试锚点的另一个优化是将AI生成的测试从简单到困难排序。这样，迭代过程就有更多机会在过程开始时获得锚点，这可以在以后迭代更复杂的人工智能测试时用作保护。
4.7 没有实际效果的探索
附录 C 中，我们介绍了我们尝试过的其他技巧和方法，但这些技巧和方法并未带来更好的结果。
5. 结果
5.1 Direct prompt 与 AlphaCodium flow 的效果对比
我们在表5.1中比较了AlphaCodium流程与单一精心设计直接提示（direct prompt）的效果。采用的评价指标是pass@k，定义为针对每个问题使用 k 个生成的解决方案，解决的问题的百分比。
Table 1: Comparison of AlphaCodium flow results to direct prompt on various models.
结果显示，无论是对开源模型（如DeepSeek）还是闭源模型（如GPT），在验证集和测试集上，AlphaCodium流程都一致地显著提升了LLMs在CodeContests问题上的性能。例如，对于GPT-4在验证集上，pass@5得分从19%提高到44%，实现了2.3倍的提升。
5.2 与先前工作的比较
我们在表5.2中将AlphaCodium的结果与文献中其他方法进行了比较。显而易见，在相同模型（GPT-3.5）和相同评价标准（pass@5）下，AlphaCodium的表现一致优于CodeChain。
与AlphaCode的对比中，我们注意到AlphaCode采用了不同的生成策略——针对代码问题特别微调了一个（未知的）模型，生成了大量的代码解决方案，进行聚类，最终从顶层聚类中选择提交K个解决方案。
例如，pass@10@100K意味着生成并聚类了100K（!）个解决方案，最终选择并提交了10个解决方案。AlphaCode使用了微调模型，并采用了显著更多LLM调用的暴力方法。尽管如此，AlphaCodium实现的最佳结果更加出色。
值得一提的是，无论是AlphaCode还是CodeChain，他们的论文都未发布一个可复制的开源解决方案，包括端到端的生成和评估脚本。评估结果时存在一些细微之处，比如如何处理有多个解决方案的问题，如何处理容错问题、超时问题等。我们基于论文报告的数据进行比较，但发布了AlphaCodium的完整可复制代码和评估脚本，使得未来的比较更加可靠一致。
5.3 与AlphaCode和AlphaCode2的计算成本比较
使用AlphaCodium流程，我们每个解决方案进行约15-20次LLM调用，因此一个pass@5 的提交大约涉及100次 LLM 调用。
AlphaCode未报告每次运行的LLM调用次数。假设每次运行进行了一次调用（未知，可能更多），那么pass@10 @100K（即，从100,000生成的解决方案中策划出的十次提交）涉及1M次LLM调用，比AlphaCodium多出四个数量级。尽管如此，AlphaCodium获得的最佳结果更加优秀。
近期，一项名为AlphaCode2的新研究，使用了Gemini-Pro模型针对编码问题进行了微调和评估。该论文同样在CodeContests基准上报告了结果，但是在一个未向公众发布的微调版本上。根据AlphaCode2的报告：“AlphaCode2只需大约100个样本就可达到AlphaCode使用一百万样本达到的性能水平，使其在样本效率上提高了10000倍。”因此，AlphaCode2和AlphaCodium在LLM调用方面比AlphaCode高出四个数量级的效率。但 AlphaCode2 利用了专门为 CodeContests 竞赛大量微调的 Gemini-Pro，而AlphaCodium使用通用模型，无需额外数据和昂贵的训练阶段即可提升性能。
6. 结论
本文中，我们引入了AlphaCodium——一个面向代码的flow，它通过不断对生成的代码进行迭代测试和修正，来应对各种输入-输出测试场景。
整个flow被划分为两个核心阶段：
预处理阶段，AlphaCodium 通过自然语言对问题进行深入思考推理； 代码迭代阶段，它在公开测试及AI生成测试基础上继续迭代优化代码。
AlphaCodium融入了我们认为对代码生成极为有益的多项设计理念、窍门和最佳实践：包括使用YAML格式进行结构化输出、生成模块化代码、通过项目符号进行深入的语义推理、双重验证的软决策、鼓励探索性思维以及利用测试锚点。
我们在一个挑战性极高的代码生成数据集——CodeContests上对AlphaCodium进行了测试。所提出的流程不仅一致地显著提升了多种闭源和开源模型的性能，还超越了文献中的先前研究成果，同时大幅度降低了计算成本。
AlphaCodium展现出的这些成果不仅证明了它在处理复杂代码生成任务方面的卓越性能，也为未来的代码生成和自动编程研究提供了新的方向和灵感。通过更高效的计算资源使用和对代码质量的持续改进，AlphaCodium为软件开发和自动化编程领域带来了创新和价值。
7. 附录
7.1 附录A Typical HumanEval code problem
/*
Check if in given vector of numbers, are any two numbers closer to each other than
given threshold. >>>
has_close_elements({1.0, 2.0, 3.0}, 0.5) false >>>
has_close_elements({1.0, 2.8, 3.0, 4.0, 5.0, 2.0}, 0.3) true
*/
#include<stdio.h>
#include<vector>
#include<math.h>
using namespace std;
bool has_close_elements(vector<float> numbers, float threshold){
7.2 附录 B 为什么 YAML 输出比 JSON 输出更适合代码生成任务
尽管最新版的GPT模型支持 JSON ，我们认为对于代码生成任务而言，YAML输出更为合适。这是因为生成的代码通常包含单引号、双引号、特殊字符等元素。LLMs在试图将这些字符准确放入JSON格式时会遇到困难，因为JSON输出必须被双引号包围（如图4(a)所示）。而YAML输出，只需遵守缩进规则，利用块标量（block scaler）表示，任何缩进正确的文本或代码都是合法的（如图4(b)所示）。
Figure 4:Comparison of the same output, once in JSON format, and once in YAML format. Taken from OpenAI playground.
此外，如图4展示，YAML格式因不需要使用大括号、引号或转义字符，所产生的Token数量比JSON少，这样不仅降低了成本和推理时间，还因为模型需要处理的非核心Token减少，从而提高了生成代码的质量。这些优势使得YAML格式更加适合复杂的代码生成任务，能有效提升生成代码的整体质量和效率。
7.3 附录C 没有实际效果的探索
我们尝试了几种方法以期提升模型在代码迭代修正中的表现，但遗憾的是，并未观察到明显的改善效果：
将失败的execution trace注入到prompt中：除了在进行迭代修复时向模型提供报错信息之外，我们还尝试向其提供最后执行的 X (50) 行的trace，希望借此提供更丰富的上下文信息，但这并未带来性能提升。 将最后 K 个失败的代码解决方案注入到prompt中：我们还试图将最近失败的几个代码解决方案注入到提示中，以期引导模型探索不同的解决路径，但这同样未能改善结果。 将最后一次 git patch diff 注入到prompt中：向模型的提示中添加最后一次 git patch diff ，也没有看到预期的改进效果。 Complicated single-stage prompts：我们尝试通过复杂的单阶段提示或系列非迭代提示来操纵和优化模型的响应，但这并未带来任何显著的进步。模型在理解长篇的问题描述时仍然面临挑战，常常忽略了关键的细节，并持续输出错误的代码。
这些尝试表明，简单地增加问题描述的复杂性或向模型提供更多的失败案例，并不能有效地提高其在代码生成任务上的性能。相反，这些方法可能由于增加了模型处理信息的负担而未能达到预期的效果，说明在改进代码生成模型时，需要更精细化和针对性的策略。
7.4 附录D 评估测试输出之间的距离
在对代码解决方案进行测试时，我们通过比较代码输出与预期输出来判断代码是否成功运行。通常，这种比较得到一个简单的bool结果：通过或失败。然而，进一步估计代码输出与正确输出之间的“距离”，对于理解代码表现和指导后续优化是非常有帮助的。为了实现这一目标，我们采用了以下方法：
若测试输出为单个数字，我们计算其与预期输出的L2距离。 若测试输出为数字数组，我们计算数组中相对应元素之间L2距离的总和。 若测试输出为字符串数组，我们逐项进行比较（布尔比较），统计不匹配的元素个数。
这种评估方式使我们能够量化CodeContests中生成的输出与正确输出之间的差异度。通过这种方法，我们不仅能判断代码是否完全正确，还能理解输出错误的程度，这对于深入分析问题和指导代码的迭代修正具有重要价值。